#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void traverse(int arr[], int size)
{
    // printf("after：\n");
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// void bubbleSort(int *arr, int size, int (*compar)(int a, int b))
// {
//     // 优化后的 降序
//     for (int i = 0; i < size - 1; i++)
//     {

//         int flag = 0; // 本轮没有交换位置
//         for (int j = 0; j < (size - 1) - i; j++)
//         {
//             // if (arr[j] - arr[j + 1] < 0)
//             if (compar(arr[j], arr[j + 1]))
//             {
//                 int tmp = arr[j];
//                 arr[j] = arr[j + 1];
//                 arr[j + 1] = tmp;

//                 // 本轮有交换位置
//                 flag = 1;
//             }
//         }
//         printf("第%d轮排序", i);
//         traverse(arr, size);
//         if (flag == 0)
//         {
//             break;
//         }
//     }
// }

// int compare(int a, int b)
// {
//     return a < b; // a大于b返回 整数 >0
// }

void bubbleSort(int *arr, int size, int (*compar)(int a, int b))
{
    // 优化后的 降序
    for (int i = 0; i < size - 1; i++)
    {

        int flag = 0; // 本轮没有交换位置
        for (int j = 0; j < (size - 1) - i; j++)
        {
            // if (arr[j] - arr[j + 1] < 0)
            if (compar(arr[j], arr[j + 1]) > 0)
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;

                // 本轮有交换位置
                flag = 1;
            }
        }
        printf("第%d轮排序", i);
        traverse(arr, size);
        if (flag == 0)
        {
            break;
        }
    }
}
int compare(int a, int b)
{
    // return a - b; // a大于b返回 整数 >0
    // return b - a; // a大于b返回 整数 >0

    if (a < b)
    {
        return 1;
    }
    else
    {
        return -1;
    }
}

int main()
{

    // int arr[] = {4, 1, 3, 1, 5, 2};
    // int arr[] = {1, 1, 4, 5, 2, 3};
    int arr[] = {1, 1, 2, 3, 4, 5};

    int size = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, size, compare);
    traverse(arr, size);

    return 0;
}
